<!DOCTYPE html>
<html lang="zh-CN">

<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1, shrink-to-fit=no">
    <link rel="shortcut icon" href="">
    <title>AStar</title>
    <style type="text/css">
        body {
            background-color: #eccc68;
        }

        canvas {
            width: 400px;
            height: 300px;
            border: 1px solid black;
        }
    </style>
</head>

<body>
    <h1>AStar</h1>
    <script type="module">
        // import * as TWO from './two.js'
        import { Scene, Render, Rect, PickContrls, Vector2 } from './two/two.js'
        // import Point from './two.js'
        // import Render from './two.js'
        const LOG = 0
        const width = 400, height = 300, edge = 40
        let cols = ~~((width * 2) / edge) - 1, rows = ~~((height * 2) / edge) - 1

        let render = new Render()
        render.setSize(width, height)
        render.setPixelRatio(2)
        // render.setTickLength(1000 / 10)
        render.setAnimationLoop(animation)
        document.querySelector('body').appendChild(render.domElement)

        const scene = new Scene()
        const colorMap = {
            0: 'hsl(220, 20%, 50%)', // 路
            1: 'hsl(120, 100%, 50%)', // 墙
            2: 'hsl(80, 20%, 50%)', // 起点
            3: 'hsl(0, 100%, 50%)',  // 终点
            4: 'hsl(40, 100%, 50%)', // 路线
            5: 'hsl(20, 80%, 50%)', // openList
            6: 'hsl(10, 80%, 50%)', // closeList
        }
        // scene.add(rect)
        // 0-路, 1-墙, 2-待选
        let map = new Array()
        for (let x = 0; x < cols; ++x) {
            map[x] = new Array()
            for (let y = 0; y < rows; ++y) {
                map[x][y] = 0
                const rect = new Rect(edge - 3, edge - 3)
                rect.setAttribute('stroke', false)
                rect.position.copy({ x: (x + 1) * edge, y: (y + 1) * edge })
                scene.add(rect)
            }
        }
        for (let x = 0; x < cols; ++x) {
            map[x][0] = 1
            map[x][rows - 1] = 1
        }
        for (let y = 0; y < rows; ++y) {
            map[0][y] = 1
            map[cols -1][y] = 1
        }

        /*
        const controls = new PickContrls(scene, render.domElement)
        controls.setPixelRatio(2)
        */
        // let x_b = ~~(Math.random() * (cols - 1)) + 1, y_b = ~~(Math.random() * (rows - 1)) + 1
        let x_b = ~~(cols / 2) + 1, y_b = ~~(rows / 2) + 1
        let end = {x: cols - 3, y: ~~((rows - 1) / 2) + 1}
        // map[x_b][y_b] = 0
        searchRoad(x_b, y_b, end.x, end.y)
        function animation() {
            render.render(scene)

            display()
        }

        function searchRoad(start_x, start_y,end_x,end_y){
            map[start_x - 2][start_y + 2] = 1
            map[start_x - 1][start_y + 2] = 1
            map[start_x + 0][start_y + 2] = 1
            map[start_x + 1][start_y + 2] = 1
            map[start_x + 1][start_y + 1] = 1
            map[start_x + 1][start_y + 0] = 1
            map[start_x + 1][start_y - 1] = 1
            map[start_x + 1][start_y - 2] = 1
            map[start_x + 0][start_y - 2] = 1
            map[start_x - 1][start_y - 2] = 1
            map[start_x - 2][start_y - 2] = 1
            map[start_x - 3][start_y - 2] = 1
            map[start_x][start_y] = 2
            map[end_x][end_y] = 3
            let closeList = []
            let openList = [{x: start_x, y: start_y, G: 0}]

            let i = 0;

            while (existList({x: end_x, y: end_y}, openList) < 0 && i++ < 1000) {
                if (openList.length > 0) {
                    let currentPoint = openList.pop()
                    closeList.push(currentPoint)
                    let surrounds = surround(currentPoint)
                    for (let i in surrounds) {
                        let item = surrounds[i]
                        if (item.x >= 0 && item.y >= 0
                            && item.x < cols && item.y < rows
                            && map[item.x][item.y] !== 1
                            && existList(item, closeList) < 0
                            && map[item.x][currentPoint.y] !== 1
                            && map[currentPoint.x][item.y] !== 1
                        ) {
                            let g = currentPoint.G + ((currentPoint.x - item.x) * (currentPoint.y - item.y) === 0 ? 10 : 14)
                            // let g = currentPoint.G + 10
                            if (existList(item, openList) < 0) {
                                item['H'] = (Math.abs(item.x - end_x) + Math.abs(item.y - end_y))  * 10
                                item['G'] = g
                                item['F'] = g + item.H
                                item['parent'] = currentPoint
                                // console.log(JSON.stringify(item))
                                openList.push(item)
                            } else {
                                let index = existList(item, openList)
                                // console.log(JSON.stringify(openList[index]), g)
                                if (g < openList[index].G) {
                                    openList[index].parent = currentPoint
                                    openList[index].G = g
                                    openList[index].F = openList[index].H + g
                                }
                            }
                        }
                    }
                }
                openList.sort((a, b)=> {return b.F - a.F})
                // openList = [openList.pop()]
                // console.log("result: " + JSON.stringify(openList))
            }
            let index = existList({x: end_x, y: end_y}, openList)
            let currentPoint =  openList[index]
            let result = []
            while(currentPoint) {
                result.unshift({x: currentPoint.x, y: currentPoint.y, G: currentPoint.G})
                currentPoint = currentPoint.parent
            }
            console.log(result)
            for (let i = 1, l = result.length - 1; i < l; ++i) {
                map[result[i].x][result[i].y] = 4
            }
        }

        //判断点是否存在在列表中，是的话返回的是序列号
        function existList(point, list) {
            for(var i in list) {
                if(point.x==list[i].x && point.y==list[i].y) {
                    return i;
                }
            }
            return -1;
        }

        function surround(pos={x: 0, y: 0}) {
            let x = pos.x, y = pos.y
            return [
                {x: x - 1, y: y - 1},
                {x: x, y: y - 1},
                {x: x + 1, y: y - 1},
                {x: x - 1, y: y},
                {x: x + 1, y: y},
                {x: x - 1, y: y + 1},
                {x: x, y: y - 1},
                {x: x + 1, y: y + 1}
            ]
        }

        function display() {
            let index = 0
            for (let x = 0; x < cols; ++x) {
                for (let y = 0; y < rows; ++y) {
                    const rect = scene.children[index++]
                    rect.setAttribute('fillStyle', colorMap[map[x][y]])
                }
            }
        }

    </script>

    <code style="width: 800px; height: 250px;word-wrap:break-word;">
        <p>AStar</p>
        <p>1. 从起点A开始, 把它作为待处理的方格存入一个"开启列表", 开启列表就是一个等待检查方格的列表.</p>
        <p>2. 寻找起点A周围可以到达的方格, 将它们放入"开启列表", 并设置它们的"父方格"为A.</p>
        <p>3. 从"开启列表"中删除起点 A, 并将起点 A 加入"关闭列表", "关闭列表"中存放的都是不需要再次检查的方格</p>
        <p>4. 把它从 "开启列表" 中删除, 并放到 "关闭列表" 中.</p>
        <p>5. 检查它所有相邻并且可以到达 (障碍物和 "关闭列表" 的方格都不考虑) 的方格. 如果这些方格还不在 "开启列表" 里的话, 将它们加入 "开启列表", 计算这些方格的 G, H 和 F 值各是多少, 并设置它们的 "父方格" 为 C.</p>
        <p>6. 如果某个相邻方格 D 已经在 "开启列表" 里了, 检查如果用新的路径 (就是经过C 的路径) 到达它的话, G值是否会更低一些, 如果新的G值更低, 那就把它的 "父方格" 改为目前选中的方格 C, 然后重新计算它的 F 值和 G 值 (H 值不需要重新计算, 因为对于每个方块, H 值是不变的). 如果新的 G 值比较高, 就说明经过 C 再到达 D 不是一个明智的选择, 因为它需要更远的路, 这时我们什么也不做.</p>
        <a href="https://www.cnblogs.com/huansky/p/5572631.html">js实现A*寻路算法</a>
        <a href="https://flatuicolors.com/palette/cn">FLAT UI COLORS 2</a>
    </code>
</body>

</html>